import java.util.LinkedList;

/**
 * @author tongchen
 * @create 2023-01-03 23:08
 */
public class Dfs {
    public static void main(String[] args) {
       bfs();
    }
   static boolean[]isVisited=new boolean[8];
    //定义数组
    static char []chars={'1','2','3','4','5','6','7','8'};
   static int[][] arr={{0,1,1,0,0,0,0,0},{1,0,0,1,1,0,0,0},{1,0,0,0,0,1,1,0},{0,1,0,0,0,0,0,1},{0,1,0,0,0,0,0,1},{0,0,1,0,0,0,1,0},{0,0,1,0,0,1,0,0},{0,0,0,1,1,0,0,0}};
    //获取第一个邻接节点
    public static int getFirstNeighbor(int index){
        for(int i=0;i<8;++i){
            if(arr[index][i]==1){
                return i;
            }

        }
        return -1;
    }
    //获取下一个邻接节点
    public static int getNextNeighbor(int  n1,int n2){
        for(int i=n2+1;i<8;++i){
            if(arr[n1][i]==1){
                return i;
            }
        }
        return -1;
    }
    //编写dfs
    public static void dfs(int[][]arr,int index){
        System.out.print(chars[index]+"->");
        isVisited[index]=true;
        int firstNeighbor = getFirstNeighbor(index);
        while(firstNeighbor!=-1){
            if(!isVisited[firstNeighbor])
            dfs(arr,firstNeighbor);
           firstNeighbor= getNextNeighbor(index,firstNeighbor);
        }



    }
    //重载方法避免单独结点
    public static void dfs(){
        for(int i=0;i<8;++i){
            if(!isVisited[i]){
                dfs(arr,i);
            }
        }
    }
    //编写bfs
    public static void bfs(int[][]arr,int i){
        int u;//记录当前访问的结点
        int w;//记录有关联的结点
        LinkedList<Integer> integers = new LinkedList<>();
        if(!isVisited[i]){
            System.out.print(chars[i]+"->");
            isVisited[i]=true;
            integers.addLast(i);
        }
        //遍历队列
        while(!integers.isEmpty()){
            u=integers.removeFirst();
            w=getFirstNeighbor(u);
            while(w!=-1){
                if(!isVisited[w]){
                    System.out.print(chars[w]+"->");
                    integers.addLast(w);
                    isVisited[w]=true;
                }
                w=getNextNeighbor(u,w);
            }
        }

    }
    //重写bfs,处理单个结点情况
    public static void bfs(){
        for (int i=0;i<8;++i){
            bfs(arr,i);
        }
    }
}
